package com.bing.java.sort;

/**
 * @author bing
 *
 * 2019年11月11日 上午10:51:51
 * 
 *  插入排序
 *  
 *  直接插入排序的最好时间复杂度,平均复杂度为O(n²)，最坏时间复杂度：O(n²)，空间复杂度：O(1)，没有分配内存。
 *  
 *  
 * 插入排序相当于向一个排好序的数组中加入新值，使得数组再次有序
 * 当第一次遍历时，相当于将第二个值与第一个比较，较小的放在前面
 * 第二次遍历时，则是将第三个值加入前两个值中合适的位置，使得三个值有序
 * ...
 * 当将最后一个值加入到前面已经排好序的数组中时，遍历结束
 */
public class SortInsert {

	public static void insSort(int[] a) {
		/**
		 * 第一次遍历(i==0)	5,3,12,8,7
		 * 			外循环
		 * 				a[j]=a[0]=5
		 * 第二次遍历(i==1)	3,5,12,8,7
		 * 			内循环
		 * 				temp = a[1] = 3
		 * 				j=i=1 j>0&&3<a[j-1]=a[0]=5 j=0
		 * 				a[1]=a[0]= 5
		 * 			外循环
		 * 				a[j]=a[0]=3
		 * 第三次遍历(i==2)	3,5,12,8,7
		 * 			内循环
		 * 				temp = a[2] = 12
		 * 			外循环
		 * 				a[2] = 12;
		 * 第四次遍历(i==3)	3,5,8,12,7
		 * 			内循环
		 * 				temp = a[3] = 8
		 * 				j=i=3 j>0&&8<a[j-1]=a[2]=12 j=2
		 * 				a[3]=a[2]= 12
		 * 			外循环
		 * 				a[2] = 8;		
		 * 第五次遍历(i==4)	3,5,7,8,12			
		 * 			内循环j==4
		 * 				temp = a[4] = 7
		 * 				j=i=4 j>0&&7<a[j-1]=a[3]=12 j=3
		 * 				a[4]=a[3]= 12
		 * 				内循环j==3
		 * 					temp = a[3] = 7
		 * 					7<a[j-1]=a[2]=8 j=2
		 * 					a[3]=a[2]=8
		 * 					
		 * 			外循环
		 * 				a[2] = 7;
		 */
		for (int i = 0; i < a.length; i++) {
			int j=0;
		    int temp = a[i];
			for (j=i;j>0&&temp<a[j-1]; j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
	}

	public static void main(String args[]) {
		int [] a = {5,3,12,8,7};
		insSort(a);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

}
